Problem statement: zenit17ska

Alternatívna stavebnica

Počet bodov: 10, časový limit: 300ms

Jožinko je expert na kreslenie rovnostranných trojuholníkov. Na začiatku nakreslí jeden rovnostranný trojuholník. V prvom kroku na každú jeho stranu prikreslí nový rovnostranný trojuholník tak, aby zdieľali práve celú jednu stranu. V ďalších krokoch toto opakuje so vzniknutým útvarom; na každú stranu útvaru prikreslí rovnostranný trojuholník so stranou dlhou ako strana útvaru (veľkosť sa vždy mení).

Koľko strán bude mať tento útvar po \(n\) krokoch?

Vstup a výstup

Na vstupe bude celé číslo \(n\) (\(1 \leq n \leq 1\,000\,000\)) - počet krokov, ktoré Jožinko vykoná. Na výstup vypíšte jedno celé číslo - počet strán, ktoré bude mať útvar po \(n\) krokoch.

 Príklad

Input:

2

Output:

3

Vstup je znázornený na obrázku.

Útvar po dvoch krokoch tak, ako postupne vznikal. Na začiatku bol biely trojuholník, v prvom kroku pribudli žlté trojuholníky, v druhom modré.